object Hello {
  def max_heapify(A: Array[Int], i: Int, heapsize: Int){
    var l = 2 * i;
    var r = 2 * i + 1;
    var largest = 0;

    if( l <= heapsize && A(l) > A(i)){
      largest = l;
    } 
    else{
      largest = i;
    }
    if( r <= heapsize && A(r) > A(largest)){
      largest = r;
    } 
    
    if(largest != i){
      var temp = 0;
      temp = A(i);
      A(i) = A(largest);
      A(largest) = temp;
      max_heapify(A, largest, heapsize);
    }
  }

  def build_max_heap(A: Array[Int], heapsize: Int){
    for( i <- A.length /2 to 1 by -1){
      max_heapify(A, i, heapsize);
    }
  }

  def heapsort(A: Array[Int]){
    var heapsize = A.length-1;
    build_max_heap(A, heapsize);
    for( i <- A.length-1 to 1 by -1 ){
      var temp = 0;
      
      temp = A(i);
      A(i) = A(1);
      A(1) = temp;
      max_heapify(A, 1, heapsize);
    }
  }
  def main(args: Array[String]){
    val N = 11;
    var A = new Array[Int](N);

    A(0) = Int.MaxValue;
    A(1) = 16;
    A(2) = 4;
    A(3) = 10;
    A(4) = 14;
    A(5) = 7;
    A(6) = 9;
    A(7)= 3;
    A(8) = 2;
    A(9) = 8;
    A(10) = 1;

    //max_heapify(A, 2, N);
    //build_max_heap(A);
    heapsort(A);
    for(i <- 1 until A.length){
      println(A(i));
    }


  }
}
